/*
lc 3040. 相同分数的最大操作数目 II
中等 2024/11/18
https://leetcode.cn/problems/maximum-number-of-operations-with-the-same-score-ii/
解答错误
175 / 549 个通过的测试用例
好难！！！
*/
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int maxScore = 0;
        int count = 0;
        int operations = 0;

        for (int i = 1; i <= sum / 2; ++i) {
            maxScore = 0;
            count = 0;
            // 尝试使用分数i进行操作
            for (int num : nums) {
                if (maxScore >= i) {
                    // 如果当前分数已经大于或等于i，那么不能再进行操作
                    break;
                }
                if (num <= i - maxScore) {
                    // 如果当前元素小于或等于i减去当前最大分数，那么可以进行操作
                    maxScore += num;
                    ++count;
                } else {
                    // 否则，我们需要找到下一个较小的元素来配对
                    maxScore = num;
                }
            }
            // 如果使用分数i可以进行的操作次数大于当前最多的操作次数，更新结果
            if (count > operations) {
                operations = count;
            }
        }
        return operations / 2; // 每次操作删除两个元素，所以需要除以2
    }
};

int main() {
    Solution solution;
    vector<int> nums = {3, 2, 1, 2, 3, 4}; // 示例1中的输入
    int result = solution.maxOperations(nums);
    cout << "最多操作次数: " << result << endl; // 应该输出 3
    return 0;
}